Recently, with the spread of mobile computers such as notebook personal computers and PDAs, there is an increasing demand for the networked computing environment capable of wirelessly connecting the mobile computers. These networks include an ad-hoc network.
The ad-hoc network does not use a dedicated router for relaying data. Each communication terminal (hereafter referred to as a node) routes messages according to the wireless communication to be able to construct a highly mobile, flexible, and economical network.
In the ad-hoc network, the wireless network is used to connect all nodes to each other. Differently from a conventional static network, the ad-hoc network is subject to very frequent changes in the topology. It is necessary to establish a route control system (routing protocol) for ensuring the reliability.
Presently suggested routing protocols for ad-hoc networks are broadly classified into two categories: on-demand and table-driven protocols. The on-demand routing protocol discovers a communication route to a communication destination immediately before initiation of the communication. According to the table-driven routing protocol, each node previously discovers a communication route to the other node irrespectively of the presence or absence of communication and maintains the detected communication route as a table. In recent years, there is proposed a hybrid routing protocol that integrates the routing protocols.
Representative on-demand routing protocols include the AODV (Adhoc On-demand Distance Vector) protocol (e.g., see patent document 1) proposed by MANET WG (Mobil Adhoc NETwork Working Group) of IETF (Internet Engineering Task Force). The following describes a route discovery process in AODV.
FIG. 25(A) shows an ad-hoc network system 1 constructed from multiple nodes A′ through E′ ands. In FIG. 25(A), nodes A′ through E′ and S′ belong to a communicable range and are connected by lines with each other. Accordingly, nodes A′ through E′ and S′ not connected by lines need to communicate with each other via the other nodes A′ through E′ and S′. In this case, the route discovery process to be described later is used to discover routes between the nodes A′ through E′ and S′ to be communicated.
For example, let us suppose that node S′ attempts to start communicating with node D′ but does not know a communication route to node D′. In such case, node S′ broadcasts a route request message (RREQ: Route Request) 2 as shown in FIG. 26.
The route request message 2 is composed of fields 31 through 39, i.e., “Type”, “Flag”, “Reserved”, “Hop Count”, “RREQ ID”, “Destination Address”, “Destination Sequence Number”, “Originator Address” and “Originator Sequence Number”. “Type” field 31 stores a message type (“1” for a route request message). “Flag” field 32 stores a flag for various communication control. “Hop Count” field 34 stores a hop count (“0” as an initial value). “RREQ ID” field 35 stores a unique ID provided for the route request message (hereafter referred to as a route request message ID).
In the route request message 2, “Destination Address” field 36 stores the address of node D′ as a transmission destination of the route request message. “Destination Sequence Number” field 37 stores the sequence number of node D′ which node S′ identified last. “Originator Address” field 38 stores the address of node S′. “Originator Sequence Number” field 39 stores the sequence number of node S′.
Each of the nodes A′ through E′ receives the route request message 2 and determines whether or not the route request message 2 is addressed to itself based on the destination of the route request message 2. The destination is stored in “Destination Address” field 36 of the route request message. When the route request message is not addressed to that node, it increments by one the hop count stored in “Hop Count” field 34 and broadcasts the route request message 2.
At this time, each of the nodes A′ through E′ checks whether or not its route table contains an address of node D′, i.e., a destination of the route request message 2. When such address is not found, each of the nodes A′ through E′ inserts various information (entries) about a reverse path to the node D′ into the route table.
The route table is referenced when receiving data to be transmitted thereafter to the destination node (node D′ in this example). As shown in FIG. 27, the route table is composed of “Destination Address”, “Destination Sequence Number”, “Hop Count”, “Next Hop”, “Precursor List”, and “Lifetime” fields 51 through 56.
During the process of inserting the reverse path into the route table 4, each of the nodes A′ through E′ copies “Destination Address”, “Destination Sequence Number”, and “Hop Count” fields 36, 37, and 34 in the route request message 2 to any of “Destination Address”, “Destination Sequence Number”, and “Hop Count” fields 51 through 53 in the route table 4.
The nodes A′ through E′ use “Next Hop” field 54 in the route table 4 to store addresses of adjacent nodes A′ through C′, E′, and S′ that transferred the route request message 2 contained in the header of the packet storing the route request message 2. This establishes a reverse path to the node D′. When data is subsequently transmitted to indicate the node D′ as a transmission destination, the data is transferred to nodes A′ through E′ having the addresses stored in the corresponding “Next Hop” field 53 based on the route table 4.
Further, the nodes A′ through E′ use “Precursor List” field 55 in the route table 4 to store a list of the other nodes A′ through E′ whose route is to be used for the communication. The nodes A′ through E′ use “Lifetime” field 56 to store the lifetime of the route. Thereafter, it is determined whether or not the entry can be alive based on the lifetime stored in “Lifetime” field 56. When the entry is not used and the lifetime expires, the entry is deleted from the route table 4.
Subsequently, the similar process takes place for the corresponding nodes A′ through E′ in the ad-hoc network system 1. Finally, the route request message 2 reaches the node D′ as the route request message transmission destination (FIG. 25(B)).
When receiving the route request message 2, each of the nodes A′ through E′ checks the route request message ID (“RREQ ID” in FIG. 26) of the route request message 2 to prevent the message from being received repeatedly. When receiving the route request message 2 with the same route request message ID in the past, the node discards the route request message 2.
There may be a case where the route request message 2 reaches the node D′ duplicatively via different routes. In such case, the node D′ gives preference to the route request message that arrived first. The second and later route request messages that arrived are discarded. This makes it possible to bidirectionally create a unique route from the node S as the transmission origin to the node D′ as the transmission destination.
On the other hand, the node D′ receives the route request message 2 to create a route reply (RREP) message 6 as shown in FIG. 28. The node D′ unicasts this message to the adjacent nodes C′ and E′ that transferred the route request message 2.
The route reply message 6 is composed of “Type”, “Flag”, “Reserved”, “Prefix Sz”, “Hop Count”, “Destination Address”, “Destination Sequence Number”, “Originator Address”, and “Lifetime” fields 71 through 79. “Type” field 71 stores a message type (“2” for the route reply message). “Flag” field 72 stores a flag for various communication control. “Prefix Sz” field 74 stores a subnet address. “Hop Count” field 75 stores a hop count (initial value is “0”).
Data for any of “Originator Address”, “Originator Sequence Number”, and “Destination Address” fields 38, 39, and 36 of the route request message 2 is copied to “Destination Address”, “Destination Sequence Number”, and “Originator Address” fields 76 through 78 of the route reply message 6.
When receiving the route reply message 6, each of the nodes C′ and E′ determines whether or not the route reply message 6 is addressed to itself based on the destination in the route reply message 6 described in “Destination Address” field 36 of the route reply message 6. When the route reply message 6 is not addressed to itself, the node increments by “1” the hop count stored in “Hop Count” field 34. The node then unicasts the route reply message 6 to nodes A′ through C′ and E′ (described in “Next Hop” field 54 of the route table 4 (FIG. 27) for the node S), i.e., the nodes configured as the reverse path for transfer of the route request message 2.
At this time, each of the nodes A′ through C′, E′, and S′ determines whether or not its route table 4 contains an address of the node D as the transmission origin of the route reply message 6. When such address does not exist, the nodes insert entries for the reverse path up to the node D into the route table 4 in a manner similar to that described with reference to FIG. 27.
A similar process subsequently takes place for the corresponding nodes A′ through C′, and E′ successively. The route reply message 6 is finally transmitted to the node S, i.e., the transmission destination of the route request message 2 (FIG. 25(C)). The node S′ receives the route reply message 6 to terminate the route discovery process.
According to AODV, each of nodes A′ through E′ and S′ discovers and configures communication routes to the communication destination node.
When an error may occur on a route between nodes available on the communication route, an error handling technique needs to be used to establish a new communication route (hereafter referred to as an alternative route) as a substitute for the current communication route.
The AODV in the on-demand routing protocol provides the local repair as such error handling technique. As shown in FIG. 29, for example, when a disconnection occurs on the route between nodes A′ and C′ on the communication route (S′-A′-C′-D′), the local repair performs the above-mentioned route discovery process using the disconnecting node A′ as a starting point to establish an alternative route (S′-A′-B′-E′-D′) to node D′.
In this case, the route table 4 (FIG. 27) may be previously enhanced to use a field to indicate a route quality state. In consideration for the route quality state, the route discovery process may be performed to establish a highly reliable alternative route (e.g., see patent document 2).
Patent document 1: U.S. Patent No. 20020049561
Patent document 2: U.S. Patent No. 005949760 (FIG. 2)
As mentioned above, the on-demand, table-driven, and hybrid routing protocols are currently proposed for ad-hoc networks. These routing protocols differ from each other in the methods of creating routes, but are common to each other in that any of these protocols only uses one route (next hop) corresponding to one destination in the route table. For example, there may be a demand for using a different route when an error occurs during communication between nodes. In such case, those protocols necessitate a wait for a new route to be created in accordance with some methods.
In this case, the on-demand protocol detects an error occurrence and then creates a new route, causing an increased overhead or time for restoration. The table-driven protocol is relatively highly resistant to errors because the routing protocol always exchanges route information. However, always exchanging information increases the overhead. Actually, it is not recommended to always exchange route information from the viewpoint of power consumption in consideration for the environment where mobile devices are connected to an ad-hoc network. On the other hand, a long cycle to update the route table may make it difficult to respond to a sudden error occurrence.
When an error occurs on the communication between nodes to disconnect the communication, for example, the above-mentioned AODV protocol creates a now route using the local repair technique of allowing nodes at both ends to transmit a message requesting rediscovery of a route. According to its architecture, the AODV protocol can create only one route at a time. When a link fails, the AODV protocol, in principle, disconnects the link and then starts creating a new route. The local repair, when capable of creating routes, could be an effective technique for the realtime communication that requires instancy.
As mentioned above, the general ad-hoc routing establishes a single route to one destination in the route table, making it difficult to provide sufficient corrective measures against error occurrences on the communication between nodes. It is difficult for the AODV, a representative on-demand routing protocol, to maintain multiple routes at a time. Even the AODV does not fully meet the requirements for error handling.
There are also proposed systems for creating multiple routes. These route control systems allow an intermediate node for maintaining routes to determine which route to use. A sending party cannot select all routes. Even when any of multiple routes can be selected, data packet originated from the same transmission origin all pass the same route. This does not ensure the effective use of multiple routes such as using different routes according to data packet attributes and freely changing routes based on the chronologically varying link quality. Generally, a long-unused route in the ad-hoc network is often automatically deleted. Even when the routing protocol is used to establish multiple routes, there are many routes that remain unused and are deleted from the route table in the long run.
For example, in the thesis “On-demand Multipath Distance Vector Routing in Ad Hoc Networks (Mahesh K. Marina, Samir R. D as, Department of Electrical & Computer Engineering and Computer Science University of Cincinnati, USA)”, there is proposed the multi-path routing as an on-demand routing protocol for creating multiple routes. However, no specification is given to a method of selecting routes.
Due to the above-mentioned problems, efficiently using multiple routes is difficult for a so-called multi-path routing protocol, i.e., a relatively highly reliable routing protocol for establishing multiple routes. It becomes especially difficult to efficiently use routes according to user requests and the link quality.
Further, the above-mentioned local repair performs the route discovery process from a point (detection point) where a given route is already disconnected even when an alternative route is established in consideration for route quality states. Accordingly, the local repair increases loads to process data which cannot be transmitted until establishment of the alternative route or prolongs the time consumed to establish the alternative route. The local repair cannot provide effective error handling for some communication types such as realtime communication that requires instancy.
A new alternative route is established from node A′ as a start point on the disconnected route. As shown in FIG. 29, the ad-hoc network subject to frequent topology changes may establish a detouring alternative route (S′-A′-B′-E′-D′) with many hop counts although there is the shortest alternative route (S′-B′-E′-D′). That is, there may be a possibility of failing to establish an optimum alternative route in accordance with frequently varying topology configurations.
On the other hand, when the route is disconnected, it may be possible to establish an alternative route from node S′ instead of the disconnecting origin. In this case, it is possible to establish an optimum alternative route in accordance with frequently varying topology configurations without establishing a detouring alternative route with many hop counts. However, there still remains the problem of increasing processing loads and the time consumption, making it difficult to provide effective error handling for some communication types such as realtime communication that requires instancy.
In this manner, the local repair establishes an alternative route from a point where the route is already disconnected, making it difficult to provide sufficient error handling depending on communication situations.
On the other hand, the table-driven protocol uses the routing protocol to always exchange route information between nodes, increasing processing loads for exchanging the route information. The table-driven protocol is not suited for communication modes such as the realtime communication requiring instancy independently of the presence or absence of error handling and the other communications requiring low power consumption.